package question.hash;

import java.util.*;

/**
 * @author: 26233
 * @create: 2022-09-24 23:24:57
 * @Description
 *
 * 一致性hash算法
 *  1. 为什么需要一致性hash
 *      在分布式系统中，普通的hash算法存在集群扩容数据迁移多(一般是缓存不命中，然后到sql中查找)，热点数据分布不均等问题
 *  2. 一致性hash原理
 *      将hash的范围分为几段，每个段对应着一个映射节点
 *  3. 使用虚拟节点解决热点数据分布不均问题
 *      将每一个物理节点映射为n个虚拟节点，再将n个虚拟节点映射为hash节点
 *      每一个物理节点的虚拟节点随机的分布在hash范围中
 *
 **/

public class ConsistentHash {

    private List<String> physicNodes = new ArrayList<>();
    private Integer virtualNodeSize = 1046789;
    private TreeMap<Long, String> virtualNodeHashToPhysicMap = new TreeMap<>();

    public ConsistentHash initPhysicNode(List<String> nodesIp) {
        physicNodes.addAll(nodesIp);
        System.out.println("nodesIp = " + nodesIp);
        return this;
    }

    private Long FNVHash(String key) {
        final int p = 16777619;
        long hash = 2166136261L;
        for (int idx = 0, num = key.length(); idx < num; ++idx) {
            hash = (hash ^ key.charAt(idx)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        if (hash < 0) {
            hash = Math.abs(hash);
        }
        return hash;
    }

    public void initVirtualNode() {
        for (String physicNode : physicNodes) {
            for (int j = 0; j < virtualNodeSize; j++) {
                virtualNodeHashToPhysicMap.put(FNVHash(physicNode + "#" + j), physicNode);
            }
        }
    }

    public String getPhysicNodeIp(String key) {
        Long hash = FNVHash(key);
        SortedMap<Long, String> longStringSortedMap = virtualNodeHashToPhysicMap.tailMap(hash);
        Long virtualNode = longStringSortedMap.isEmpty() ? virtualNodeHashToPhysicMap.firstKey() : longStringSortedMap.firstKey();
        return virtualNodeHashToPhysicMap.get(virtualNode);
    }

    public static void main(String[] args) {
        ConsistentHash consistentHash = new ConsistentHash();
        List<String> nodesIp = Arrays.asList("192.168.56.2", "192.168.56.3", "192.168.56.4", "192.168.56.5");
        consistentHash.initPhysicNode(nodesIp).initVirtualNode();

        //add
        for (int i = 0; i < 10; i++) {
            System.out.println(consistentHash.getPhysicNodeIp(new Object().toString()));
        }

    }

}
